home *** CD-ROM | disk | FTP | other *** search
/ Java Programmer's Toolkit / Java Programmer's Toolkit.iso / applets / collectn / rbpair.jav < prev    next >
Text File  |  1995-12-14  |  4KB  |  183 lines
  1. /*
  2.   File: RBPair.java
  3.  
  4.   Originally written by Doug Lea and released into the public domain. 
  5.   Thanks for the assistance and support of Sun Microsystems Labs, Agorics 
  6.   Inc, Loral, and everyone contributing, testing, and using this code.
  7.  
  8.   History:
  9.   Date     Who                What
  10.   24Sep95  dl@cs.oswego.edu   Create from collections.java  working file
  11.   13Oct95  dl                 Changed protection statuses
  12.  
  13. */
  14.   
  15. package collections;
  16.  
  17. import java.util.Enumeration;
  18. import java.util.NoSuchElementException;
  19.  
  20. /**
  21.  *
  22.  * RBPairs are RBCells with keys.
  23.  *
  24.  * @author Doug Lea
  25.  * @version 0.93
  26.  *
  27.  * <P> For an introduction to this package see <A HREF="index.html"> Overview </A>.
  28. **/
  29.  
  30. public class RBPair extends RBCell implements Pair {
  31.  
  32. // instance variable
  33.  
  34.   private Object   key_;
  35.  
  36. /**
  37.  * Make a cell with given key and element values, and null links
  38. **/
  39.  
  40.   public RBPair(Object k, Object v)           { super(v); key_ = k; }
  41.  
  42. /**
  43.  * Make a new node with same key and element values, but null links
  44. **/
  45.  
  46.   protected Object clone() throws CloneNotSupportedException { 
  47.     RBPair t = new RBPair(key_, element());
  48.     t.color_ = color_;
  49.     return t;
  50.   }
  51.  
  52. /**
  53.  * return the key
  54. **/
  55.  
  56.   public final Object key()           { return key_; }
  57.  
  58. /**
  59.  * set the key
  60. **/
  61.  
  62.   public final void   key(Object k)   { key_ = k; }
  63.  
  64. /**
  65.  * Implements RBCell.find.
  66.  * Override RBCell version since we are ordered on keys, not elements, so
  67.  * element find has to search whole tree.
  68.  * comparator argument not actually used.
  69.  * @see RBCell#find
  70. **/
  71.  
  72.   public RBCell find(Object element, Comparator cmp) {
  73.  
  74.     RBCell t = this;
  75.     while (t != null) {
  76.       if (t.element().equals(element)) return t;
  77.       else if (t.right_ == null)
  78.         t = t.left_;
  79.       else if (t.left_ == null) 
  80.         t = t.right_;
  81.       else {
  82.         RBCell p = t.left_.find(element, cmp);
  83.         if (p != null) return p;
  84.         else
  85.           t = t.right_;
  86.       }
  87.     }
  88.     return null; // not reached
  89.   }
  90.  
  91. /**
  92.  * Implements RBCell.count.
  93.  * @see RBCell#count
  94. **/
  95.   public int count(Object element, Comparator cmp) {
  96.     int c = 0;
  97.     RBCell t = this;
  98.     while (t != null) {
  99.       if (t.element().equals(element)) ++c;
  100.       if (t.right_ == null)
  101.         t = t.left_;
  102.       else if (t.left_ == null) 
  103.         t = t.right_;
  104.       else {
  105.         c += t.left_.count(element, cmp);
  106.         t = t.right_;
  107.       }
  108.     }
  109.     return c;
  110.   }
  111.  
  112. /**
  113.  * find and return a cell holding key, or null if no such
  114. **/
  115.  
  116.   public RBPair findKey(Object key, Comparator cmp) {
  117.     RBPair t = this;
  118.     for (;;) {
  119.       int diff = cmp.compare(key, t.key_);
  120.       if (diff == 0) return t;
  121.       else if (diff < 0) t = (RBPair)(t.left_);
  122.       else t = (RBPair)(t.right_);
  123.       if (t == null) return null;
  124.     }
  125.   }
  126.  
  127. /**
  128.  * find and return a cell holding (key, element), or null if no such
  129. **/
  130.   public RBPair find(Object key, Object element, Comparator cmp) {
  131.     RBPair t = this;
  132.     for (;;) {
  133.       int diff = cmp.compare(key, t.key_);
  134.       if (diff == 0 && t.element().equals(element)) return t;
  135.       else if (diff <= 0) t = (RBPair)(t.left_);
  136.       else t = (RBPair)(t.right_);
  137.       if (t == null) return null;
  138.     }
  139.   }
  140.  
  141. /**
  142.  * return number of nodes of subtree holding key
  143. **/
  144.   public int countKey(Object key, Comparator cmp) {
  145.     int c = 0;
  146.     RBPair t = this;
  147.     while (t != null) {
  148.       int diff = cmp.compare(key, t.key_);
  149.       // rely on insert to always go left on <=
  150.       if (diff == 0) ++c;
  151.       if (diff <= 0) t = (RBPair)(t.left_);
  152.       else t = (RBPair)(t.right_);
  153.     }
  154.     return c;
  155.   }
  156.  
  157. /**
  158.  * return number of nodes of subtree holding (key, element)
  159. **/
  160.   public int count(Object key, Object element, Comparator cmp) {
  161.     int c = 0;
  162.     RBPair t = this;
  163.     while (t != null) {
  164.       int diff = cmp.compare(key, t.key_);
  165.       if (diff == 0) {
  166.         if (t.element().equals(element)) ++c;
  167.         if (t.left_ == null)
  168.           t = (RBPair)(t.right_);
  169.         else if (t.right_ == null)
  170.           t = (RBPair)(t.left_);
  171.         else {
  172.           c += ((RBPair)(t.right_)).count(key, element, cmp);
  173.           t = (RBPair)(t.left_);
  174.         }
  175.       }
  176.       else if (diff < 0) t = (RBPair)(t.left());
  177.       else t = (RBPair)(t.right());
  178.     }
  179.     return c;
  180.   }
  181. }
  182.  
  183.